package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class UglyNumberIi {
    // 2022-09-04 19:33:02
    public static void main(String[] args) {
        Solution solution = new UglyNumberIi().new Solution();
        solution.nthUglyNumber(10);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Map<Integer, Boolean> map = new HashMap();

        public int nthUglyNumber(int n) {
//            return timeOver(n);
            int[] dp = new int[n + 1];
            int p2 = 1, p3 = 1, p5 = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
                if (dp[i] == dp[p2] * 2) {
                    p2++;
                }
                if (dp[i] == dp[p3] * 3) {
                    p3++;
                }
                if (dp[i] == dp[p5] * 5) {
                    p5++;
                }
            }
            return dp[n];

        }

        private int timeOver(int n) {
            if (n <= 5) return n;
            int count = 5;
            map.put(1, true);
            map.put(2, true);
            map.put(3, true);
            map.put(4, true);
            map.put(5, true);
            int num = 6;
            while (count < n) {
                if (judge(num, 2) || judge(num, 3) || judge(num, 5)) {
                    count++;
                    map.put(num, true);
                }
                num++;
            }
            return num - 1;
        }

        private boolean judge(int num, int param) {
            return num % param == 0 && map.getOrDefault(num / param, false);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}